#include <stdio.h>
#include <stdlib.h>

typedef struct LNode
{
    char data;
    struct LNode *next;
} LNode, *SqStack;

//带头结点
void InitStack(SqStack &S)
{
    S = (LNode *)malloc(sizeof(LNode));
    S->next = NULL;
}

//判空
bool isEmpty(SqStack S)
{
    return S->next == NULL;
}

void Push(SqStack &S, char x)
{

    LNode *p = (LNode *)malloc(sizeof(LNode));
    p->data = x;
    p->next = S->next;
    S->next = p;
}

bool Pop(SqStack &S, char &x)
{
    if (isEmpty(S))
    {
        return false;
    }

    x = S->next->data;
    S->next = S->next->next;
    // free(S->next);
    return true;
}

bool getTopElem(SqStack S, char &x)
{
    if (isEmpty(S))
    {
        return false;
    }
    x = S->next->data;
    return true;
}

void print(SqStack S)
{
    while (S->next != NULL)
    {
        printf("%c\n", S->next->data);
        S = S->next;
    }
}

//括号匹配
/*
遇到左括号入栈，遇到右括号则出栈与之匹配

*/
bool barketCheck(char *str, int length)
{
    SqStack S;
    InitStack(S);
    for (int i = 0; i < length; i++)
    {
        if (str[i] == '[' || str[i] == '(' || str[i] == '{')
        {
            Push(S, str[i]);
        }
        else
        {
            if (isEmpty(S))
            {
                return false;
            }
            char topElem;
            Pop(S, topElem);
            if (str[i] == ')' && topElem != '(')
            {
                return false;
            }
            if (str[i] == ']' && topElem != '[')
            {
                return false;
            }
            if (str[i] == '}' && topElem != '{')
            {
                return false;
            }
        }
    }
    return isEmpty(S);
}

/*
波兰表达式：前缀表达式
逆波兰表达式：后缀表达式

后缀表达式怎么算：
左优先原则：只要左边的运算符能计算，就优先计算左边的
依次扫描表达式：
若出现运算符，从栈中弹出两个数字并执行相应的运算，把结果压入栈中

前缀表达式怎么算：
右优先原则：只要右边的运算符能计算，就优先计算右边的

*/

/*
中缀转后缀表达式：
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况:
   ①遇到操作数。直接加入后缀表达式。
   ②遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到
    弹出“(” 为止。注意:“(” 不加入后缀表达式。
   ③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，
    若碰到“(”或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

*/

char *zhongToHou(char *str, int length)
{
    int count = 0;
    char *result;
    SqStack S;
    InitStack(S);
    for (int i = 0; i < length; i++)
    {
        if (str[i] >= 48 && str[i] <= 57) //如果是数字
        {
            result[count++] = str[i];
        }
        if (str[i] == '(')
        {
            Push(S, str[i]);
        }
        if (str[i] == ')')
        {
            char topElem;
            while (true)
            {
                Pop(S, topElem);
                if (topElem == '(')
                {
                    break;
                }
                else
                {
                    result[count++] = topElem;
                }
            }
        }
        else //如果是运算符
        {
            char topElem;
            if (str[i] == '*' || str[i] == '/')
            {
                while (true)
                {
                    getTopElem(S, topElem);
                    if (topElem == '*' || topElem == '/')
                    {
                        result[count++] = topElem;
                        Pop(S, topElem);
                    }
                    else
                    {
                        break;
                    }
                }
            }
            else
            {
            }
        }
    }

    return result;
}

//用栈实现后缀表达式的计算
/*
1、从左扫描下一个元素，直到处理完所有元素
2、若扫描到操作数则压入栈，并回到1，否则执行3
3、若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果回压栈栈中，回到1
*/

//用栈实现前缀表示值的计算
/*
1、从右扫描下一个元素，直到处理完所有元素
2、若扫描到操作数则压入栈，并回到1，否则执行3
3、若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果回压栈栈中，回到1
*/

/**
 * @brief  后缀表达式求值
 *
 * @param str 后缀表达式
 * @param length 表达式长度
 * @param res    计算结果
 * @return true
 * @return false
 */
bool resOfHou(char *str, int length, int &res)
{
    SqStack S;
    char A, B; //每次运算的操作数
    InitStack(S);
    for (int i = 0; i < length; i++)
    {
        if (str[i] >= '0' || str[i] <= '9')
        {                    //如果是数字
            Push(S, str[i]); //直接入栈
        }
        else
        {
            if (isEmpty(S))
            {
                return false;
            }
            Pop(S, B);
            if (isEmpty(S))
            {
                return false;
            }
            Pop(S, A);
            if (str[i] == '+')
            {
                Push(S, A + B);
            }
            else if (str[i] == '-')
            {
                Push(S, A - B);
            }
            else if (str[i] == '*')
            {
                Push(S, A * B);
            }
            else
            {
                Push(S, A / B);
            }
        }
    }
    return true;
}

/*
中缀表达式计算结果：
用栈实现中缀表达式的计算:
初始化两个栈，操作数栈和运算符栈
若扫描到操作数，压入操作数栈
若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出
运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，
运算结果再压回操作数栈)

*/

int main()
{
    printf("\n\n========================================================================\n\n");
    SqStack S;
    char *str = "(([)))";
    bool flag = barketCheck(str, 6);
    printf("成功与否%d", flag);
    printf("\n\n========================================================================\n\n");
    return 0;
}